package com.smzh.service;

import java.util.ArrayList;
import java.util.List;

/**
 * 回文
 * 
 * @author jun
 *
 */
/*
 * 给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。
 * 
 * 返回s所有可能的回文串分割方案。
 */
/*
 * 先做一个动态规划，保存i到j的字串是否是回文串，减小之后的重复计算。
 * 
 * 然后dfs去搜索满足条件的分割方式，sign记录当前元素之后是否进行了分割。
 * 
 * index记录dfs对于字符串的遍历深度，当等于长度的时候就是一种符合条件的情况，根据之前sign的分割，把字串数组存入result
 */
public class Palindrome {

	// 保存计算结果
	private List<List<String>> result = new ArrayList<List<String>>();

	// 标记i到j的状态
	private int[][] dp = new int[1024][1024];

	// sign记录当前元素之后是否进行了分割
	private int[] sign = new int[1024];

	public List<List<String>> partition(String s) {
		if (s == null || s.length() <= 0) {
			return null;
		}
		int len = s.length();
		for (int i = 0; i < len; i++) {
			for (int j = i; j < len; j++) {
				for (int k = 0; k <= (j - i + 1) / 2; ++k) {// 判断i到j区间的字段是否为回文
					if (s.charAt(i + k) != s.charAt(j - k))
						break;// 不是回文退出
					if (k == (j - i + 1) / 2)
						dp[i][j] = 1;// 标记i到j为回文
				}
			}
		}
		dfs(s, 0);
		return result;
	}

	//递归
	public void dfs(String s, int index) {
		if (index == s.length()) {// 计算
			List<String> f = new ArrayList<String>();
			String temp = "";
			for (int i = 0; i < s.length(); ++i) {
				temp += s.charAt(i);
				if (sign[i] == 1) {
					f.add(temp);
					temp = "";
				}
			}
			if (f.size() > 0) {
				result.add(f);
			}
			return;
		}
		for (int i = index; i < s.length(); ++i) {
			if (dp[index][i] == 1) {
				sign[i] = 1;// sign记录当前元素之后是否进行了分割
				dfs(s, i + 1);
				sign[i] = 0;
			}
		}
	}

	public static void main(String[] args) {
		Palindrome palindrome = new Palindrome();
		System.out.println(palindrome.partition("AAB"));
	}
}
